

class Solution {
    vector<int> tmp;
public:
    vector<int> sortArray(vector<int>& nums) {
        int n=nums.size();
        tmp.resize(n);
        mergeSort(nums,0,n-1);
        return nums;
    }

    void mergeSort(vector<int>& nums,int left,int right)
    {
        if(left>=right) return;

        //1.选择中间点划分
        int mid=(left+right)/2;

        //2.左右区间排序
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);

        //3.合并排序
        int cur1=left,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=right)
        {
            tmp[i++]=nums[cur1]>nums[cur2]?nums[cur2++]:nums[cur1++];
        }
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=right) tmp[i++]=nums[cur2++];

        //4，还原
        for(int i=left;i<=right;i++)
        {
            nums[i]=tmp[i-left];
        }
    }
};